The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2).

(0) Obligation:

The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

a(h, h, h, x) → s(x)
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) → a(l, x, z, z)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))
s(h) → 1
app(nil, k) → k
app(l, nil) → l
app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))

Rewrite Strategy: INNERMOST

(1) DependencyGraphProof (BOTH BOUNDS(ID, ID) transformation)

The following rules are not reachable from basic terms in the dependency graph and can be removed:
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))

(2) Obligation:

The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

a(l, x, s(y), h) → a(l, x, y, s(h))
sum(cons(x, nil)) → cons(x, nil)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
app(cons(x, l), k) → cons(x, app(l, k))
app(nil, k) → k
app(l, nil) → l
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(h, h, h, x) → s(x)
a(l, s(x), h, z) → a(l, x, z, z)
s(h) → 1

Rewrite Strategy: INNERMOST

(3) NestedDefinedSymbolProof (BOTH BOUNDS(ID, ID) transformation)

The following defined symbols can occur below the 0th argument of sum: s, a
The following defined symbols can occur below the 0th argument of a: s, a
The following defined symbols can occur below the 1th argument of a: s, a

Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))

(4) Obligation:

The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
app(nil, k) → k
app(l, nil) → l
a(h, h, h, x) → s(x)
a(l, s(x), h, z) → a(l, x, z, z)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
s(h) → 1

Rewrite Strategy: INNERMOST

(5) CpxTrsToCdtProof (BOTH BOUNDS(ID, ID) transformation)

Converted Cpx (relative) TRS to CDT

(6) Obligation:

Complexity Dependency Tuples Problem
Rules:

app(cons(z0, z1), z2) → cons(z0, app(z1, z2))
app(nil, z0) → z0
app(z0, nil) → z0
sum(cons(z0, nil)) → cons(z0, nil)
sum(cons(z0, cons(z1, z2))) → sum(cons(a(z0, z1, h, h), z2))
a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
+(z0, h) → z0
+(h, z0) → z0
s(h) → 1

Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
APP(nil, z0) → c1
APP(z0, nil) → c2
SUM(cons(z0, nil)) → c3
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(h, h, h, z0) → c6(S(z0))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
+'(z0, h) → c8
+'(h, z0) → c9
S(h) → c10

S tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
APP(nil, z0) → c1
APP(z0, nil) → c2
SUM(cons(z0, nil)) → c3
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(h, h, h, z0) → c6(S(z0))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
+'(z0, h) → c8
+'(h, z0) → c9
S(h) → c10

K tuples:none
Defined Rule Symbols:

app, sum, a, +, s

Defined Pair Symbols:

APP, SUM, A, +', S

Compound Symbols:

c, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10

(7) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID) transformation)

Removed 7 trailing nodes:

A(h, h, h, z0) → c6(S(z0))
+'(h, z0) → c9
S(h) → c10
+'(z0, h) → c8
APP(nil, z0) → c1
APP(z0, nil) → c2
SUM(cons(z0, nil)) → c3

(8) Obligation:

Complexity Dependency Tuples Problem
Rules:

app(cons(z0, z1), z2) → cons(z0, app(z1, z2))
app(nil, z0) → z0
app(z0, nil) → z0
sum(cons(z0, nil)) → cons(z0, nil)
sum(cons(z0, cons(z1, z2))) → sum(cons(a(z0, z1, h, h), z2))
a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
+(z0, h) → z0
+(h, z0) → z0
s(h) → 1

Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

S tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

K tuples:none
Defined Rule Symbols:

app, sum, a, +, s

Defined Pair Symbols:

APP, SUM, A

Compound Symbols:

c, c4, c5, c7

(9) CdtUsableRulesProof (EQUIVALENT transformation)

The following rules are not usable and were removed:

app(cons(z0, z1), z2) → cons(z0, app(z1, z2))
app(nil, z0) → z0
app(z0, nil) → z0
sum(cons(z0, nil)) → cons(z0, nil)
sum(cons(z0, cons(z1, z2))) → sum(cons(a(z0, z1, h, h), z2))
+(z0, h) → z0
+(h, z0) → z0

(10) Obligation:

Complexity Dependency Tuples Problem
Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1

Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

S tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

K tuples:none
Defined Rule Symbols:

a, s

Defined Pair Symbols:

APP, SUM, A

Compound Symbols:

c, c4, c5, c7

(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))

We considered the (Usable) Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1

And the Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

The order we found is given by the following interpretation:
Polynomial interpretation :

POL(1) = 0   
POL(A(x₁, x₂, x₃, x₄)) = 0   
POL(APP(x₁, x₂)) = x₁   
POL(SUM(x₁)) = x₁   
POL(a(x₁, x₂, x₃, x₄)) = 0   
POL(c(x₁)) = x₁   
POL(c4(x₁, x₂)) = x₁ + x₂   
POL(c5(x₁)) = x₁   
POL(c7(x₁)) = x₁   
POL(cons(x₁, x₂)) = [1] + x₁ + x₂   
POL(h) = 0   
POL(s(x₁)) = 0   

(12) Obligation:

Complexity Dependency Tuples Problem
Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1

Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

S tuples:

A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

K tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))

Defined Rule Symbols:

a, s

Defined Pair Symbols:

APP, SUM, A

Compound Symbols:

c, c4, c5, c7

(13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))

We considered the (Usable) Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1

And the Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

The order we found is given by the following interpretation:
Polynomial interpretation :

POL(1) = 0   
POL(A(x₁, x₂, x₃, x₄)) = x₁   
POL(APP(x₁, x₂)) = 0   
POL(SUM(x₁)) = x₁   
POL(a(x₁, x₂, x₃, x₄)) = [1] + x₄   
POL(c(x₁)) = x₁   
POL(c4(x₁, x₂)) = x₁ + x₂   
POL(c5(x₁)) = x₁   
POL(c7(x₁)) = x₁   
POL(cons(x₁, x₂)) = [1] + x₁ + x₂   
POL(h) = 0   
POL(s(x₁)) = [1] + x₁   

(14) Obligation:

Complexity Dependency Tuples Problem
Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1

Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

S tuples:

A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

K tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))

Defined Rule Symbols:

a, s

Defined Pair Symbols:

APP, SUM, A

Compound Symbols:

c, c4, c5, c7

(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

We considered the (Usable) Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1

And the Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

The order we found is given by the following interpretation:
Polynomial interpretation :

POL(1) = 0   
POL(A(x₁, x₂, x₃, x₄)) = [1] + x₂ + [2]x₄ + x₄² + x₁·x₄   
POL(APP(x₁, x₂)) = x₁·x₂   
POL(SUM(x₁)) = x₁   
POL(a(x₁, x₂, x₃, x₄)) = [1] + [2]x₄   
POL(c(x₁)) = x₁   
POL(c4(x₁, x₂)) = x₁ + x₂   
POL(c5(x₁)) = x₁   
POL(c7(x₁)) = x₁   
POL(cons(x₁, x₂)) = [2] + x₁ + x₂   
POL(h) = 0   
POL(s(x₁)) = [1] + [2]x₁   

(16) Obligation:

Complexity Dependency Tuples Problem
Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1

Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

S tuples:none
K tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))

Defined Rule Symbols:

a, s

Defined Pair Symbols:

APP, SUM, A

Compound Symbols:

c, c4, c5, c7

(17) SIsEmptyProof (BOTH BOUNDS(ID, ID) transformation)

The set S is empty

(18) BOUNDS(1, 1)